/* 

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N  共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

 

示例 1：

输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
示例 2：

输入：K = 2, N = 6
输出：3
示例 3：

输入：K = 3, N = 14
输出：4
 

提示：

1 <= K <= 100
1 <= N <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/super-egg-drop
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

// 解法1（优先）: 时间复杂度->O(KN)
var superEggDrop = function (K, N) {
    const dp = Array(K + 1).fill(0).map(() => new Array(N + 1).fill(0))
    // console.log(dp)

    let m = 0;
    while (dp[K][m] < N) {
        m++;
        for (let k = 1; k <= K; k++) {
            dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
        }
    }

    return m;
};

// 解法2:
/* var superEggDrop = function (K, N) {
    // 不选择dp[K][M]的原因是dp[M][K]可以简化操作
    const dp = Array(N + 1)
        .fill(0)
        .map((_) => Array(K + 1).fill(0));

    let m = 0;
    while (dp[m][K] < N) {
        m++;
        for (let k = 1; k <= K; ++k) dp[m][k] = dp[m - 1][k - 1] + 1 + dp[m - 1][k];
    }
    return m;
}; */

// 解法3（力扣超时）：
/* let superEggDrop = function (k, n) {
    let memo = Array(k + 1).fill(0).map(() => new Array(n + 1).fill(0))

    let dp = function (k, n) {
        // base case
        if (n === 0) return 0;
        if (k === 1) return n;
        // 避免重复计算
        if (memo[k][n]) return memo[k][n];

        let res = Infinity;
        // 穷举所有可能
        for (let i = 1; i <= n; i++) {
            res = Math.min(res, Math.max(
                dp(k, n - i), // 没碎
                dp(k - 1, i - 1) // 碎
            ) + 1) // 在i楼扔了一次
        }
        // 记入备忘录
        memo[k][n] = res;
        return res;
    }

    return dp(k, n);
}

console.log(superEggDrop(3, 15)) */

// 解法4：
/* let superEggDrop = function (k, n) {
    if (n < 1)
        return 0;
    if (k == 1)
        return n;
    let logtimes = Math.floor(Math.log2(n)) + 1;
    if (k >= logtimes)
        return logtimes;
    let f = new Array(k + 1);
    f.fill(0);
    let cnt = 0;
    while (f[k] < n) {
        ++cnt;
        for (let i = k; i > 0; --i)
            f[i] += f[i - 1] + 1;
    }
    return cnt;
}

console.log(superEggDrop(3, 15)) */